/*
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
*/

int countPrimes(int n)
{
    int *nums = malloc(sizeof(int) * n);
    int res = 0;
    int i = 0;
    int k = 2;

    for (i = 0; i < n; i++){
        nums[i] = 1;
    }
    for (i = 2; i <= sqrt(n); i++) {
        if (nums[i]) {
            k = 2;
            while (k * i < n) {
                nums[k * i] = 0;
                k++;
            }
        }
    }

    
    for (i =  2; i < n; i++) {
        res += nums[i];
    }
    return res;
}

